package leetcode.sword;

import java.io.*;
import java.util.Arrays;

public class Solution40 {

    public static int cout = 0;
    public static void main(String[] args) throws IOException {
        int[] arr=new int[20];
        InputStreamReader inputStreamReader = new InputStreamReader(new FileInputStream(new File("E:\\arr.txt")));
        BufferedReader bufferedReader= new BufferedReader(inputStreamReader);
        String line = null;
        int i=0;
        //按行读取
        while((line = bufferedReader.readLine() )!= null&&i<20){
            if(null != line){
                //依次转换为int类型存入到分配好空间的数组中
                arr[i] = Integer.valueOf(line);
                //行数加1
                i++;
            }
        }
//        Random rd = new Random();
//        for(int i=0;i<arr.length;i++){
//            arr[i]=rd.nextInt(1000);
//        }
//        int[] arr = {0,0,1,2,4,2,2,3,1,4};
//        int k = 200;
        Solution40 s = new Solution40();
        s.getLeastNumbers(arr,10);
//        for (int num:arr) {
//            System.out.println(num);
//        }
        System.out.println(cout);

    }

//    //快排 416ms
    public int[] getLeastNumbers(int[] arr, int k) {
        long time = System.currentTimeMillis();
        int len = arr.length;
        if(len*k==0) return new int[0]; //len=0 或 k=0
        if(k==len) return arr;

        int left = 0, right = len-1;
        int valid = 0; //确定位置的元素
        while(valid!=k){ //把排好的
            valid = quickSort(arr, left, right);
            if(valid>k) right = valid-1;
            if(valid<k) left = valid+1;
        }
        System.out.println("time:"+(System.currentTimeMillis()-time));
        return Arrays.copyOf(arr, k);
    }

    public int quickSort(int[] arr, int i, int j){ //对arr从i到rigth的元素快排，返回枢轴量的位置
        cout ++;
        if(cout==8);
        if(i==j) return i;
        int tmp = arr[i];
        while(i<j){
            while(i<j&&arr[j]>=tmp) j--;
            arr[i] = arr[j];
            while(i<j&&arr[i]<=tmp) i++;
            arr[j] = arr[i];
        }
        arr[i] = tmp;
        System.out.println(i);
        return i;
    }

    //快排 2ms
     public int[] getLeastNumbers1(int[] arr, int k) {
        long time = System.currentTimeMillis();
        int len = arr.length;
        if(len*k==0) return new int[0]; //len=0 或 k=0
        if(len==k) return arr;
        int[] res = quickSort1(arr, k, 0, len - 1);
        System.out.println("time:"+(System.currentTimeMillis()-time));
        return res;
     }

     public int[] quickSort1(int[] arr, int k, int l, int r){ //对arr从i到rigth的元素快排，返回枢轴量的位置
        cout ++;
        int i = l, j = r, tmp = arr[l];
       while(i<j){
         while(i<j&&arr[j]>=tmp) j--;
         arr[i] = arr[j];
         while(i<j&&arr[i]<=tmp) i++;
         arr[j] = arr[i];
       }
       arr[i] = tmp;
       System.out.println(i);
       if (i > k) return quickSort1(arr, k, l, i - 1);
       if (i < k) return quickSort1(arr, k, i + 1, r);
       return Arrays.copyOf(arr, k);
     }

}
